#ifndef BITREE_H_

#define BITREE_H_

#include <iostream>
#include <queue>
#include "status.h"
using namespace std;

class Tree
{
private:
	struct Node
	{
		char data;
		Node * lChild, * rChild;
	};

	Node * head;
	Status getData(Node * & n);
	Status prePrintData(Node * n) const;
public:
	Tree();
	~Tree();
	Status preTraverse() const;
	bool isCompleteTree() const;
};

Status Tree::getData(Node * & n)
{
	char ch;
	cin.get(ch);
	if (ch == '#')
		return ERROR;
	Node * tmp = new Node;
	tmp->rChild = nullptr;
	tmp->lChild = nullptr;
	tmp->data = ch;
	n = tmp;

	getData(n->lChild);
	getData(n->rChild);

	return OK;
}

Tree::Tree()
{
	head = nullptr;
	cout << "input data by PreOrder ('#' means nullptr)" << endl;
	getData(head);
}

Tree::~Tree()
{

}

Status Tree::prePrintData(Node * n) const
{
	if (!n)
		return OK;
	cout << n->data << endl;
	prePrintData(n->lChild);
	prePrintData(n->rChild);

	return OK;
}

Status Tree::preTraverse() const
{
	prePrintData(head);

	return OK;
}

Status Tree::preTraverse() const
{

}

bool Tree::isCompleteTree() const
{
	queue<Node *> NodeQue;
	if (!head)
		return false;
	NodeQue.push(head->lChild);
	NodeQue.push(head->rChild);
	bool out = 0;
	while (!out)
	{
		queue<Node *> tmpQue;
		out = 1;
		bool check = 1;
		int len = NodeQue.size();
		for (int i = 0; i < len; i++)
		{
			const Node * x = NodeQue.front();
			NodeQue.pop();
			if (!x)
				check = 0;
			else if (!check)
				return false;
			else
			{
				out = 0;
				tmpQue.push(x->lChild);
				tmpQue.push(x->rChild);
			}
		}

		NodeQue = tmpQue;
	}

	return true;
}

#endif